
#include"Queue.h"
void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = ps->tail = NULL;//初始化将指向队头与队尾的指针指向空
}

void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;//定义cur 保存第一个节点的指针
	while (cur) // 销毁要一个节点一个节点的删除，进行遍历
	{
		QNode* next = cur->next; //保存下一个节点的指针，以防将该节点释放后找不到下一个节点的地址
		free(cur);
		cur = next; // 指针后移
	}
	ps->head = ps->tail = NULL;//别忘了
}


//队尾入
void QueuePush(Queue* ps,QDatatype x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//插入新元素时开辟空间
	if (newnode == NULL)// 若malloc失败则终止程序
	{
		perror("malloc");
		exit(-1);
	}
	newnode->next = NULL; //将新开辟节点初始化
	newnode->data = x;
	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode; //若队列为空则是第一个元素，头尾是同一个元素
	}
	else {
		ps->tail->next = newnode;//队尾节点指向下一个要插入元素的节点
		ps->tail = newnode;//更新队尾节点
	}
}

//队头出
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head);//空队列判定，无法进行删除（出）元素操作
	if (ps->head->next == NULL)//若队列只有一个元素
	{
		ps->head = ps->tail = NULL;
	}
	else//删除元素从队头开始删除
	{
		QNode* next = ps->head->next;//保存队头元素的下一个元素地址
		free(ps->head);//释放队头元素
		ps->head = next;//队头指针后移
		//注意else 中的操作步骤
	}
}

QDatatype QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->head);//空队列终止
	return ps->head->data;	 //返回队头元素//出队列时 队头元素先出
}

QDatatype QueueBcack(Queue* ps)//含义同上
{
	assert(ps);
	assert(ps->head);
	return ps->tail->data;
}

bool QueueEmpty(Queue* ps)//判读队列是否为空
{
	assert(ps);
	return ps->head == NULL;
}

int QueueSize(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	QNode* cur = ps->head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}